The present invention relates to error correction mechanisms and methods for data blocks that are divided into portions or parts, which may involve datagrams, segments, packets, frames or fragments. This may have particular applicability in computer and other networks, especially for devices that can communicate over a network using Transport Control Protocol (TCP) over Internet Protocol (IP). Recent advances in this area include intelligent network interface hardware and software that has been developed by Alacritech, Inc. to work with a host computer. Detailed descriptions of such advances, as well as relevant claims, can be found in U.S. Pat. Nos. 6,226,680, 6,226,680, 6,247,060, 6,334,153, 6,389,479, 6,393,487, 6,427,171, 6,427,173, 6,434,620 and 6,470,415, which are incorporated by reference herein.
A Cyclic Redundancy Check (CRC) is a known mechanism for detecting errors in data storage or transmission. A CRC is generally performed by treating a block of data as a unit having a numerical value, and then dividing that numerical value by a selected divisor to obtain a remainder that is characteristic of the block of data. The remainder may be appended to the block of data before transferring the data, for example over a network or bus, so that upon receipt of the data another CRC can be performed on the received data, which is compared with the received remainder to assure data integrity. Somewhat confusingly, the remainder that results from dividing the block of data by the divisor is often itself called a CRC.
CRC calculations are commonly performed with a shift register that is coupled to logic gates to perform division of blocks of data. The data may be represented as a polynomial with each data bit serving as a coefficient of the polynomial, while another polynomial may serve as the divisor for the CRC calculation. A polynomial is a value expressed in a particular algebraic form, such as: AXn+BXn−1+ . . . +CX1+DX0, where successive powers of X are the orders and the multipliers A, B, C and D are the coefficients. Our common number system is an implied polynomial of base 10. That is, each digit of a number is multiplied by its associated power of 10 and added to each other digit multiplied by its associated power of 10 to derive a value for the number. The base 2 or binary system of numeration is also a form of the general polynomial concept.
Arithmetic modulo m is arithmetic in which at every stage of a calculation we remove all possible multiples of m, and consider only the remainders. For instance if we were to add 5 and 7, modulo 9, we would first compute 5+7=12, but then remove 9, to result in 3.
The polynomials used in conventional CRC calculations can be manipulated with polynomial modulo two arithmetic, which allows a relatively fast and direct hardware implementation of division for error detection. Modulo 2 operations are performed logically, in which the addition operation is a logical exclusive-OR (XOR) of the values, and modulo two subtraction is exactly the same XOR operation. Thus it is conventional for CRC calculations to divide a block of data, which can be viewed as a polynomial having a numerical value, by feeding the data into a shift register that is coupled to XOR gates corresponding to the polynomial divisor.
Often a block of data is separated into portions that are packaged as segments, datagrams, packets, or frames for transmission from one device to another. For example, Ethernet Protocol specifies a maximum segment size (MSS) of 1518 bytes, which may be implemented by protocols such as TCP (Transport Control Protocol) and IP (Internet Protocol) that separate data blocks into approximately 1.4 KB packets for transmission as Ethernet frames. Each frame contains a CRC, which may be called a frame check sequence (FCS) for detecting errors in that frame.
Asynchronous Transfer Mode (ATM) protocol specifies performing a CRC calculation on a message that is transmitted over a network as segments that are then reassembled, after which the CRC is checked. To do this a CRC calculation is first performed on the message and appended to it, and the message is separated into segments having exactly 48 bytes of data and 5 byte headers that are required to be transmitted and received in order. The segments are then received and the data concatenated to form the message, and then a second CRC calculation is performed on the received message and checked against the appended CRC. The unvarying size of ATM segments and the guarantee that ATM segments are received in order can be used to facilitate calculation of the CRC on the message composed of the segments.
Unlike ATM, Ethernet frames containing TCP or UDP (User Datagram Protocol) data may arrive in a different order from that with which they were sent. Moreover, a particular network may specify a MSS that differs from 1518B, and a last frame of a message will likely be less than the MSS. Further, TCP, IP and UDP header lengths may vary depending upon a number of variables (e.g., IP4 vs. IP6, TCP options, optional timestamps, etc.), and a device must be prepared to receive the frames containing those variable length headers in any order. Thus a block of data that is divided into portions prepended with TCP/IP headers or UDP/IP headers may have variable portion lengths and frames that are received out of order.
Internet SCSI (iSCSI) is an evolving network storage protocol that may require that a CRC be performed on blocks of data that are communicated over networks via TCP/IP packets. For transmission of iSCSI data between devices, a CRC remainder may be appended to a block of data that is then divided by TCP into multiple packets each having a TCP/IP header for transmission over a network, with only one of the packets having an iSCSI header. In this case, the indefinite packet length and order of the packets as received can make calculating a CRC on received data problematic. For example, temporary storage may need to be allocated to buffer all the received packets for a message so that iSCSI data from the packets can reordered and CRC tested. Particularly for the situation in which multiple iSCSI connections are handled by a network port and plural network ports are employed by a single host, providing sufficient memory resources to handle CRC calculations may be expensive.